/**
 * 4.寻找两个郑旭数组的中位数
 */
public class Exerciser1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 求中位数，就是相当于是求取 第k小的数
        // 因为是 合并后的两个数组是严格递增的
        // 那么可以使用 二分的方法+递归 进行计算
        int n = nums1.length;
        int m = nums2.length;
        // 进行计算求第k小的数，也就是中位数
        // 如果 n+m整个数组为偶数，那么就是计算中间的两位
        // 如果 n+m整个数组为奇数，那么就是计算中间的值两次
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;

        return (getMid(nums1,0,n - 1,nums2,0,m - 1,left) + getMid(nums1,0,n - 1,nums2,0,m - 1,right)) * 0.5;
    }

    public double getMid(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k) {
        // 计算长度
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        // 保证len1 是最短的那一个
        if(len1 > len2) return getMid(nums2,start2,end2,nums1,start1,end1,k);
        if(len1 == 0) {
            // 如果len1为0，那么说明 nums1中无数据，直接在nums2中进行寻找
            return nums2[start2 + k - 1]; // k是比数组下标大一位的
        }

        if(k == 1) {
            // 表示start位置就是当前的对应要找的k位置值
            return Math.min(nums1[start1],nums2[start2]);
        }

        // 计算从start位置开始 到达 k/2 位置的下标，这里需要比较 长度和k/2 的大小，取小值
        // 因为k位置是大于下标一位的，需要进行-1
        int i = start1 + Math.min(len1,k / 2) - 1;
        int j = start2 + Math.min(len2,k / 2) - 1;
        if(nums1[i] < nums2[j]) {
            // 谁小越过谁，因为每个数组都是严格递增的，那么比当前位置都大的话，那么比它前面的位置值都大
            // 越过这个对应的长度之后，需要把 k 进行减小，需要减从i位置到达开始位置的值，再+1，因为k比下标大一位
            return getMid(nums1,i + 1,end1,nums2,start2,end2,k - (i - start1 + 1));
        }else {
            return getMid(nums1,start1,end1,nums2,j + 1,end2,k - (j - start2 + 1));
        }
    }
}
